This invention relates generally to communicating data securely, and more particularly to a cryptographic system and methods of using public key cryptography.
Computer systems are found today in virtually every walk of life for storing, maintaining, and transferring various types of data. The integrity of large portions of this data, especially that portion relating to financial transactions, is vital to the health and survival of many commercial enterprises. Individual consumers also have an increasing stake in data security as open and unsecure data communications channels for sales transactions, such as credit card transactions over the Internet, gain popularity.
Protecting data stored in computer memory, tape, and disk is often important. However, just as important, if not more so, is the ability to transfer financial transactions or other communications from a sender to an intended receiver without intermediate parties being able to interpret the transferred message. Furthermore, as important transactions are increasingly handled electronically, authentication of the originator of a message must be ensured. For example, for electronic banking, there needs to be a way to authenticate that an electronic document, such as a bank draft, has actually been xe2x80x9csignedxe2x80x9d by the indicated signatory.
Cryptography, especially public key cryptography, has proven to be an effective and convenient technique of enhancing data privacy and authentication. Data to be secured, called plaintext, is transformed into encrypted data, or ciphertext by a predetermined encryption process of one type or another. The reverse process, transforming ciphertext into plaintext, is termed decryption. In public key cryptography, the processes of encryption and decryption are controlled by a pair of related cryptographic keys. A xe2x80x9cpublicxe2x80x9d key is used for the encryption process, and a xe2x80x9cprivatexe2x80x9d key is used to decrypt ciphertext. Alternatively, the private key may be used to encrypt the data, and the public key to decrypt it. This latter method provides a method of digitally signing data to positively identify the source of the data.
The prior art includes a number of public key schemes. However, over the past decade, one system of public key cryptography has gained popularity. Known generally as the xe2x80x9cRSAxe2x80x9d scheme, it is now thought by many to be a worldwide defacto standard for public key cryptography. The RSA scheme is described in U.S. Pat. No. 4,405,829.
The RSA scheme capitalizes on the relative ease of creating a composite number from the product of two prime numbers whereas the attempt to factor the composite number into its constituent primes is difficult. Pairs of public/private keys can then be found based on the factors of the composite number. A message is encrypted using a series of mathematical exponentiations and divisions based on one of the keys. If the matching key of the public/private key pair is known, the message can be decrypted using a series of mathematical exponentiations and divisions using the matching key. The composite number is a part of the public and private keys so it is known to the public. However, since the private key can only be found by factoring the composite number, calculating the private key from the public key is computationally difficult.
The security of the RSA technique can be enhanced by increasing the difficulty of factoring the composite number through judicious choices of the prime numbers. (This, of course would be true for any encryption/decryption scheme using or requiring prime numbers.) Another, and principle enhancement, is to increase the length (i.e., size) of the composite number. Today, it is common to find RSA schemes being proposed in which the composite number is on the order of 600 digits long. The task of exponentiating a number this long, however, can be daunting and time consuming, although not as difficult as factoring. Therefore, increasing the length of the composite number increases the security, but only at the expense of increased time to perform the encryption and decryption.
However, recently discovered techniques have greatly improved the efficiency with which encryption/decryption functions are performed using the RSA scheme. Rather than using two prime numbers to form the composite number conventionally employed in RSA cryptographic operations, it has been found that more than two prime numbers can also be used. In addition, it has also been found that the Chinese Remainder Theorem can be used to break an RSA encryption or decryption task into smaller parts that can be performed much faster than before.
In addition to the security of the data, another important issue with regard to cryptographic systems is the security of the system itself. In a system implementing an encryption algorithm, ensuring that the system is secure from tampering is important. One area of concern is the secure loading and storing of application programs for the system. If the application program can be altered or substituted, the security of a system may be breeched.
It is therefore desirable to provide an efficient cryptographic system for implementing public key cryptography with multiple prime factors. It is also desirable to provide a cryptographic system that may be initialized to a secure state while providing maximum flexibility for the user in providing application programs to the system.
A cryptographic system is provided having a processor and a plurality of exponentiation units. The processor receives encryption or decryption requests from a host processor and divides them into one or more exponentiation tasks. These exponentiation tasks are transferred to one or more execution units that perform the exponentiation and return a value to the processor. This allows the exponentiations tasks to be performed in parallel, thereby decreasing the time needed to perform the encryption and decryption requests.
The present invention further provides a method of initializing the cryptographic system in a secure manner. An external memory holds a first program file along with header information, a hash value, and a digital signature in an encrypted program packet. The first program file contains a key/option table holding an RSA cryptographic public key. A processor loads the encrypted program packet and decrypts it using a cryptographic key, however the resulting program file is only executed by the processor after authenticating it. If it cannot be authenticated, then the cryptographic keys are zeroed out, and the cryptographic system is put into a non-functioning state.
The first program file is authenticated by checking the header for proper format, computing an expected hash value of the first program file and comparing it with the hash value, and checking the digital signature with an RSA public key that is stored in the cryptographic system.
After authenticating this first program file, the processor executes the first program file. The first program file loads a second program file from the external memory. This second program file is generally a user-application program. It is authenticated in a similar manner to the first program file, but the digital signature is checked against the RSA public key found in the key/option table.
By this initialization process, the user of the cryptographic system may load personalized application programs with secret cryptographic keys not known to anyone else. The process ensures that the application programs cannot be altered or substituted with fraudulent programs. At the same time, the manufacturer of the cryptographic system can securely provide maintenance and upgrade programs over public networks, and ensure that only properly licensed users are using the programs.
A further understanding of the nature and advantages of the inventions presented herein may be realized by reference to the remaining portions of the specification and the attached claims.